#ifndef BST_TREE_H
#define BST_TREE_H

#include <iostream>
#include <functional>
#include <memory>
#include <queue>
#include <stack>
#include <unistd.h>
#include <vector>
#include <map>

using std::cout;
using std::endl;
using std::less;
using std::map;
using std::queue;
using std::shared_ptr;
using std::stack;
using std::vector;

template <typename T, typename Compare = less<T>>
class BST
{
public:
    struct Node
    {
        // 使用零构造
        Node(T val = T()) : val_(val), left_(nullptr), right_(nullptr) {}
        T val_;
        Node *left_;
        Node *right_;

        bool operator<(const Node *rhs) const
        {
            return val_ < rhs->val_;
        }

        bool operator==(const Node *rhs) const
        {
            return val_ == rhs->val_;
        }
    };

    Node *root_;
    Compare comp_;

private:
    int high(Node *node) const
    {
        if (!node)
            return 0;
        int left = high(node->left_);
        int right = high(node->right_);
        return left > right ? left + 1 : right + 1;
    }

    int num(Node *node) const
    {
        if (!node)
            return 0;
        int left = num(node->left_);
        int right = num(node->right_);
        return left + right + 1;
    }

    void levelOrder(Node *node, int i) const
    {
        if (!node)
            return;
        if (i == 0)
        {
            cout << node->val_ << " ";
            return;
        }
        levelOrder(node->left_, i - 1);
        levelOrder(node->right_, i - 1);
    }

    Node *recursion_insert(Node *node, T val)
    {
        if (!node)
        {
            return new Node(val);
        }

        if (node->val_ == val)
            return node;
        else if (!comp_(node->val_, val))
        {
            node->left_ = recursion_insert(node->left_, val);
        }
        else
        {
            node->right_ = recursion_insert(node->right_, val);
        }
        return node;
    }

    Node *recursion_erase(Node *node, T val)
    {
        if (!node)
            return nullptr;
        else if (node->val_ == val)
        {
            Node *pre = nullptr;
            if (node->left_ && node->right_)
            {
                pre = node->left_;
                while (pre->right_)
                {
                    pre = pre->right_;
                }
                node->val_ = pre->val_;
                node->left_ = recursion_erase(node->left_, pre->val_);
                return node;
            }

            Node *child = node->left_;
            if (!child)
                child = node->right_;

            delete node;
            return child;
        }
        else if (!comp_(node->val_, val))
        {
            node->left_ = recursion_erase(node->left_, val);
        }
        else
        {
            node->right_ = recursion_erase(node->right_, val);
        }
        return node;
    }

    bool recursion_contain(Node *node, T val) const
    {
        if (!node)
            return false;
        if (node->val_ == val)
            return true;
        else if (!comp_(node->val_, val))
        {
            return recursion_contain(node->left_, val);
        }
        else
        {
            return recursion_contain(node->right_, val);
        }
    }

    void queryElems(Node *node, vector<T> &ret, T lhs, T rhs)
    {
        if (node)
        {
            if (!comp_(node->val_, lhs))
                queryElems(node->left_, ret, lhs, rhs);
            if (node->val_ >= lhs && node->val_ <= rhs)
                ret.push_back(node->val_);
            if (comp_(node->val_, rhs))
                queryElems(node->right_, ret, lhs, rhs);
        }
    }

    bool isBST(Node *node, Node *&pre) const
    {
        if (node)
        {
            if (!isBST(node->left_, pre))
            {
                return false;
            }
            if (pre)
            {
                if (comp_(node->val_, pre->val_))
                {
                    return false;
                }
            }

            pre = node;
            return isBST(node->right_, pre);
        }
        else
        {
            return true;
        }
    }

    bool isChild(Node *node, Node *rhs) const
    {
        // 如果两个节点同时为null，那么就是相同
        if (!node && !rhs)
            return true;
        // 如果子树为空，那么直接返回 true
        if (!rhs)
            return true;
        // 如果字数不为空，并且母树为空，直接返回 false
        if (!node)
            return false;

        if (node->val_ != rhs->val_)
        {
            return false;
        }
        if (!isChild(node->left_, rhs->left_))
        {
            return false;
        }
        return isChild(node->right_, rhs->right_);
    }

    bool isChild(Node *node, BST<T, Compare> &rhs) const
    {
        if (!node)
            return false;
        if (node->val_ == rhs.root_->val_)
        {
            return isChild(node, rhs.root_);
        }
        else if (!comp_(node->val_, rhs.root_->val_))
        {
            return isChild(node->left_, rhs);
        }
        else
        {
            return isChild(node->right_, rhs);
        }
    }

    void LCAFind(Node *node, map<Node *, int> &ret, const T &val) const
    {
        while (node)
        {
            if (node->val_ == val)
            {
                return;
            }
            else if (!comp_(node->val_, val))
            {
                ret[node]++;
                node = node->left_;
            }
            else
            {
                ret[node]++;
                node = node->right_;
            }
        }
        for (auto &[key, val] : ret)
        {
            val = 1;
        }
    }

    Node *lastestParent(Node *node, map<Node *, int> &ret, const T &lhs, const T &rhs) const
    {
        LCAFind(node, ret, lhs);
        LCAFind(node, ret, rhs);
        bool min = false;
        Node *retN = root_;
        if (lhs < root_->val_ && rhs < root_->val_)
            min = true;
        for (auto &val : ret)
        {
            if (min && val.second == 2)
            {
                if (retN->val_ > val.first->val_)
                {
                    retN = val.first;
                }
            }
            else if (val.second == 2)
            {
                if (retN->val_ < val.first->val_)
                {
                    retN = val.first;
                }
            }
        }
        return retN;
    }

    Node *getLCA(Node *node, const T &lhs, const T &rhs) const
    {
        if (!node)
            return nullptr;

        if (comp_(node->val_, lhs) && comp_(node->val_, rhs))
        {
            getLCA(node->right_, lhs, rhs);
        }
        else if (comp_(lhs, node->val_) && comp_(rhs, node->val_))
        {
            getLCA(node->left_, lhs, rhs);
        }
        else
        {
            return node;
        }
    }

    void mirror(Node *node)
    {
        if (!node)
            return;
        Node *tmp = node->left_;
        node->left_ = node->right_;
        node->right_ = tmp;
        mirror(node->left_);
        mirror(node->right_);
    }

    bool isSymmetry(Node *lhs, Node *rhs) const
    {
        // 如果两个节点同时为nullptr，返回true
        if (!lhs && !rhs)
            return true;
        // 如果有一个节点为nullptr，程序执行结束
        else if (!lhs || !rhs)
            return false;
        else if (lhs->val_ != rhs->val_)
        {
            return false;
        }

        return isSymmetry(lhs->left_, rhs->right_) && isSymmetry(lhs->right_, rhs->left_);
    }

    /*            i  i+1           i+(k-m)              j
        eg: pre-> 58, 24, 0, 5, 34, 41, 67, 62, 64, 69, 78
                  m                 k                    n
            in -> 0, 5, 24, 34, 41, 58, 62, 64, 67, 69, 78

        依次根据前序遍历的头元素作为当前根节点，此时
            在前序遍历中的左子树元素为 i+1 ~ i+(k-m), 右子树的元素为 i+(k-m)+1 ~ j
            在中序遍历中的左子树元素为 m ~ k-1, 右子树的元素为 k+1 ~ n
    */
    Node *_rebuild(T *pre, int i, int j, T *in, int m, int n)
    {
        if (i > j || m > n)
        {
            return nullptr;
        }

        // 通过前序遍历的头元素构建根节点
        Node *node = new Node(pre[i]);
        for (int k{m}; k <= n; k++)
        {
            if (pre[i] == in[k])
            {
                node->left_ = _rebuild(pre, i + 1, i + (k - m), in, m, k - 1);
                node->right_ = _rebuild(pre, i + (k - m) + 1, j, in, k + 1, n);
                return node;
            }
        }
        return node;
    }

    // 使用形参记录当前节点的高度。当遍历到当前分支的空节点是，返回高度
    int isBalance(Node *node, int l, bool &flag) const
    {
        // 如果当前节点为nullptr， 返回当前分支的高度
        if(!node)
            return l;
        
        // 记录左子树的高度
        int left = isBalance(node->left_, l + 1, flag);
        // 如果不是平衡树，直接返回，不在判断
        if(!flag)  
            return left;
        // 记录右子树的高度
        int right = isBalance(node->right_, l + 1, flag);
        if(!flag)
            return right;

        // 判断是否符合平衡二叉树
        if(abs(left - right) > 1){
            flag = false;
        }

        // 返回当前分支的最大高度
        return left > right ? left: right;
    }
    int i = 1;
    Node *getKVal(Node *node, int k) 
    {
        if(!node)
            return nullptr;
        
        Node *left = getKVal(node->right_, k);  // R
        // 如果获得结果，直接返回
        if(left) return left;
        // 处理的个数++
        if(i++ == k)                        // V
            return node;
        
        return getKVal(node->left_, k );   // L
    }

    Node *preGetV(Node *node, int k)
    {
        if(!node) return nullptr;
        Node *right = preGetV(node->right_, k);// R
        if(right) return right;
        Node *left = preGetV(node->left_, k); // L
        if(left) return left;

        if(i++ == k)
            return node;
    }

    void destruct(Node *node, stack<Node *> &stk)
    {
        if(!node)
            return ;

        stk.push(node);
        destruct(node->left_, stk);
        destruct(node->right_, stk);
    }

public:
    BST() : root_(nullptr) {}
    ~BST()
    {
        if(!root_) return;
        queue<Node *> que;
        que.push(root_);
        Node *front = nullptr;
        while(!que.empty()){
            front = que.front();
            que.pop();
            if(front->left_)
                que.push(front->left_);
            if(front->right_)
                que.push(front->right_);
            

            delete front;
        }
    }
/*     ~BST() 
    {
        stack<Node *> stk;
        destruct(root_, stk);
        while(!stk.empty()){
            delete stk.top();
            stk.pop();
        }
        root_ = nullptr;
    } */

    // 求出中序遍历的倒数第K个, 可以转换为后序遍历的整数第K个
    // 中序    L V R -> R V L
    Node *getKVal(int k) 
    {
        i = 1;
        return getKVal(root_, k);
    }

    Node *preGetV(int k)
    {
        i = 1;
        return preGetV(root_, k);
    }

    // 判断是否为平衡二叉树（左右子树的高度差最多为1）
    bool isBalance() const
    {

        bool flag = true;
        isBalance(root_, 0, flag);
        return flag;
    }

    void rebuild(T *pre, int i, int j, T *in, int m, int n)
    {
        root_ = _rebuild(pre, i, j, in, m, n);
    }

    void mirror()
    {
        if (!root_)
            return;
        mirror(root_);
    }

    bool isSymmetry() const
    {
        if (!root_)
            return true;
        return isSymmetry(root_->left_, root_->right_);
    }

    // LCA 最近公共祖先节点
    T getLCA(const T &lhs, const T &rhs) const
    {
        if (!root_ || !contain(lhs) || !contain(rhs))
            throw "No LCA";

        return getLCA(root_, lhs, rhs)->val_;
    }

    Node *lastestParent(const T &lhs, const T &rhs) const
    {
        if (!root_)
            return nullptr;
        if (!contain(lhs) || !contain(rhs))
            return nullptr;
        map<Node *, int> ret;
        return lastestParent(root_, ret, lhs, rhs);
    }

    // 判断BST是否为当前BST的子树
    bool isChild(BST<T, Compare> &rhs) const
    {
        if (!rhs.root_)
            return true;
        return isChild(root_, rhs);
    }

    // 利用中序遍历升序的特性，判断当前树是否为BST树
    bool isBST() const
    {
        Node *pre = nullptr;
        return isBST(root_, pre);
    }

    void queryElems(vector<T> &ret, T lhs, T rhs)
    {
        queryElems(root_, ret, lhs, rhs);
    }

    void levelForeach() const
    {
        Node *front = nullptr;
        queue<Node *> que;
        if (root_)
            que.push(root_);
        while (!que.empty())
        {
            front = que.front();
            que.pop();
            cout << front->val_ << " ";
            if (front->left_)
                que.push(front->left_);
            if (front->right_)
                que.push(front->right_);
        }
        cout << endl;
    }

    void lastForeach() const
    {
        stack<Node *> stk, result;
        Node *node = root_;
        if (node)
            stk.push(node);
        while (!stk.empty())
        {
            node = stk.top();
            stk.pop();
            if (node->left_)
                stk.push(node->left_);
            if (node->right_)
                stk.push(node->right_);
            result.push(node);
        }
        while (!result.empty())
        {
            cout << result.top()->val_ << " ";
            result.pop();
        }
        cout << endl;
    }

    void preForeach() const
    {
        Node *top = nullptr;
        stack<Node *> stk;
        stk.push(root_);
        while (!stk.empty())
        {
            top = stk.top();
            stk.pop();

            if (top->right_)
                stk.push(top->right_);
            if (top->left_)
                stk.push(top->left_);

            cout << top->val_ << " ";
        }
        cout << endl;
    }

    void inForeach() const
    {
        stack<Node *> stk;
        Node *node = root_;

        while (!stk.empty() || node)
        {
            if (node)
            {
                stk.push(node);
                node = node->left_;
            }
            else
            {
                node = stk.top();
                stk.pop();
                cout << node->val_ << " ";
                node = node->right_;
            }
        }

        cout << endl;
    }

    bool recursion_contain(T val) const
    {
        return recursion_contain(root_, val);
    }

    void recursion_insert(T val)
    {
        root_ = recursion_insert(root_, val);
    }

    void recursion_erase(T val)
    {
        root_ = recursion_erase(root_, val);
    }

    void levelOrder() const
    {
        int h = high();
        for (int i{}; i < h; i++)
        {
            levelOrder(root_, i);
        }
        cout << endl;
    }

    void n_levelOrder() const
    {
        queue<T> que;
        int h = high();
        for (int i{}; i < h; i++)
        {
            Node *node = root_;
            for (int k{i}; k != 0; k--)
            {
                node = node->left_;
            }
            node = root_;
            que.push(node->val_);
            for (int k{i}; k != 0; k--)
            {
                node = node->right_;
            }
            que.push(node->val_);
        }

        while (!que.empty())
        {
            cout << que.front() << " ";
        }
        cout << endl;
    }

    int num() const
    {
        return num(root_);
    }

    int high() const
    {
        return high(root_);
    }

    bool contain(const T &val) const
    {
        if (!root_)
            return false;
        Node *node = root_;
        while (node)
        {
            if (node->val_ == val)
                return true;
            else if (!comp_(node->val_, val))
            {
                node = node->left_;
            }
            else
            {
                node = node->right_;
            }
        }
        return false;
    }

    void erase(T val)
    {
        if (!root_)
            return;
        // 如果删除的是叶子节点，直接删除就好，如果删除的是非叶子节点，可以将其左子树的大值/右子树的最小值进行替换，然后删除最大/最小值节点
        Node *node = root_, *parent = nullptr;
        while (node)
        {
            if (node->val_ == val)
                break;
            else if (!comp_(node->val_, val))
            {
                parent = node;
                node = node->left_;
            }
            else
            {
                parent = node;
                node = node->right_;
            }
        }

        if (!node)
            return;
        // 要删除节点的左右子树都不为空
        Node *remNode = node;
        if (node->left_ && node->right_)
        {
            parent = node;
            node = node->left_;
            while (node->right_)
            {
                parent = node;
                node = node->right_;
            }
            remNode->val_ = node->val_;
            remNode = node;
        }

        Node *child = remNode->left_;
        if (!child)
        {
            child = remNode->right_;
        }

        if (!parent)
        {
            root_ = child;
        }
        if (parent && parent->left_ == remNode)
        {
            parent->left_ = child;
        }
        else if (parent)
        {
            parent->right_ = child;
        }

        delete node;
    }

    void insert(T val)
    {
        // 插入数据，首先创建节点，找到合适的位置，插入
        Node *node = new Node(val);
        if (!root_)
        {
            root_ = node;
        }
        else
        {
            Node *tmp = root_, *pre = nullptr;
            while (tmp)
            {
                if (tmp->val_ == val)
                {
                    return;
                }
                else if (comp_(tmp->val_, val))
                {
                    pre = tmp;
                    tmp = tmp->right_;
                }
                else
                {
                    pre = tmp;
                    tmp = tmp->left_;
                }
            }
            if (!comp_(pre->val_, val))
                pre->left_ = node;
            else
                pre->right_ = node;
        }
    }

    void midEach(Node *node)
    {
        if (!node)
            return;
        midEach(node->left_);
        cout << node->val_ << " ";
        midEach(node->right_);
    }

    void foreach ()
    {
        midEach(root_);
        cout << endl;
    }
};

#endif